package main.java.com.gxc.string;

import java.util.Stack;

/**
 * 最长有效括号长度
 */
public class LongestValidBracket {

    public static void main(String[] args) {
        int size = 10000;
        for (int i = 0; i < size; i++) {
            String str = randomStr();
            if (process2(str)!=dpProcess(str) || dpProcess(str) != noExtraSpaceProcess(str)) {
                System.out.println(str);
                System.out.println("算法有问题");
                break;
            }
        }

        String a = ")((()()";
        System.out.println(dpProcess(a));
        System.out.println(noExtraSpaceProcess(a));
    }

    private static String randomStr() {
        StringBuffer stringBuffer = new StringBuffer();
        int size = (int) (Math.random()*1000);
        for (int i = 0; i < size; i++) {
            int gl = (int) (Math.random()*2);
            if (gl ==0) {
                stringBuffer.append("(");
            } else {
                stringBuffer.append(")");
            }
        }
        return stringBuffer.toString();
    }

    public static int process2(String str) {
        if (str == null || str.equals("")) return 0;

        //最长有效括号长度
        int max = 0;
        Stack<Integer> stack = new Stack<>();
        //处理边界条件，默认加入一个值，不需要判断栈是否为空，判断最大长度时，先弹出 字符 (，i-栈顶 即可，
        stack.push(-1);
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == ')' && stack.size()>1 && str.charAt(stack.peek()) == '(') {
                //配对的 ( 弹出
                stack.pop();
                //当前位置减去栈顶 就是最大长度
                max = Math.max(max, i-stack.peek());
            } else {
                stack.push(i);
            }
        }

        return max;
    }

    /**
     * dp 处理
     * @param str
     * @return
     */
    public static int dpProcess(String str) {
        if (str == null || str.equals("")) return 0;

        char[] chars = str.toCharArray();
        int[] dp = new int[chars.length];
        int max = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == ')') {
                //i位置前的是 ( 可配对,初始位置不可匹配
                if (i==0) {
                    dp[i] = 0;
                } else if (chars[i-1] =='('){
                    //如果i前一个位置是 (, 则可配对，
                    dp[i] = 2 + (i>1?dp[i-2]:0);
                } else if (chars[i-1]==')') {
                    //如果i前一个位置是 ), 从i位置往一直往前找 (排除已匹配后 dp[i-1]) 的第一个字符(i- dp[i-1]-1)，如果是 ( , 则配对
                    //如果配对成功，则需要是否能和 i- dp[i-1]-2 连成一个更长的有效括号长度  (())(())  譬如这种情况
                    if (i-1-dp[i-1]>=0 && chars[i-1-dp[i-1]] == '(') {
                        dp[i] = 2 + dp[i-1];
                        if (i- 2 -dp[i-1]>=0) dp[i] += dp[i- 2 -dp[i-1]];
                    }
                }

                max = Math.max(max, dp[i]);
            } else if (chars[i] == '('){
                dp[i] = 0;
            }
        }
        return max;
    }

    public static int noExtraSpaceProcess(String str) {
        //最长有效括号长度
        int max = 0;
        // ( 的数量
        int left = 0;
        // ) 的数量
        int right = 0;

        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '(') {
                left++;
            } else {
                right++;
            }
            //最长的有效括号，肯定是 ( ) 数量相等的时候
            if (right == left) {
                max = Math.max(max, left);
            } else if (right>left) {
                //当 ) 的数量大于 ( 的数量时， ()()), 数量重置
                left = 0;
                right = 0;
            }
        }

        //应对(()***的情况
        left = 0;
        right = 0;
        for (int i = chars.length-1; i >=0; i--) {
            if (chars[i] == '(') {
                left++;
            } else {
                right++;
            }
            //当 ) 的数量小于 ( 的数量时， ()()), 数量重置
            if (right == left) {
                max = Math.max(max, left);
            } else if (right<left) {
                left = 0;
                right = 0;
            }
        }
        return max*2;
    }

}
